#include <iostream>
using namespace std;

int search_cycle(int *a, int s, int e, int key);
int binarysearch(int *a, int s, int e, int key);

int main(int argc, char *argv[])
{
    int a[] = {1,3,4,5,-3,-2,-1};
    //int a[] = {1,2,3,4,5};

    int len = sizeof(a)/sizeof(a[0]);
    for (int i = 0; i < len; i++) {
        cout << search_cycle(a, 0, sizeof(a)/sizeof(a[0])-1, i) << ' ';
    }
    
    return 0;
}

int search_cycle(int *a, int s, int e, int key)
{
    if (s > e) 
        return -1;
    
    int m = s + (e - s)/2;
    
    if (a[m] == key)
        return m;
    else if (a[m] > key) {
        if (a[s] <= a[m]) {
            if (a[m] > a[e] && a[s] > key)
                return search_cycle(a, m+1, e, key);
            else 
                return binarysearch(a, s, m-1, key);
        }
        else { // a[s] > a[m], s2 sorted
            return search_cycle(a, s, m-1, key);
        }
    }
    else { // a[m] < key
        if (a[s] <= a[m]) {
            if (a[m] <= a[e]) 
                return binarysearch(a, m+1, e, key);
            else if (a[m] > a[e]) {
                return search_cycle(a, m+1, e, key);
            }
        }
        else { // a[m] < a[s], s2 sorted
            if (key <= a[e])
                return binarysearch(a, m+1, e, key);
            else 
                return search_cycle(a, s, m-1, key);
        }

    }

}

int binarysearch(int *a, int s, int e, int key)
{
    if (s > e)
        return -1;

    int mid;
    while (s <= e) {
        mid = s + (e-s)/2;
        if (a[mid] == key)
            return mid;
        else if(a[mid] > key) 
            e = mid-1;
        else 
            s = mid+1;
    }
    return -1;

}
